package interview.huawei.tjt.training.huisu;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
 *
 * 示例 1: 输入: 2 输出: 1
 *
 * 解释: 2 = 1 + 1, 1 × 1 = 1。
 *
 * 示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 说明: 你可以假设 n 不小于 2 且不大于 58。
 */
// 回溯法求解
public class IntegerBreak {

    private static List<Integer> result = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            helper(n,1,0,1);
            Collections.sort(result);
            System.out.println(result.get(result.size() - 1));
//            System.out.println(result);
            result.clear();
        }
    }

    private static void helper (int n, int startIndex, int sum, int product) {
        if (sum == n) {
            result.add(new Integer(product));
            return;
        }

        for (int i = startIndex; i < n; i ++) {
            if (sum + i > n) break;
            helper(n, i, sum + i, product * i);
//            sum = sum - i;
//            product = product / i;
        }
    }


}
